package 左哥算法.ch06二叉树;

import org.junit.Test;

import java.util.*;

public class Ch02层序遍历 {
    /**
     * ch01
     */
    @Test
    public void test01() {
        TreeNode treeNode = new TreeNode();
        treeNode.newTree(3);
        levelOrder01(treeNode).forEach(System.out::print);
    }

    /**
     * ch01:不分层的层序遍历
     * 思路：
     * 1.预先将头节点入队
     * 2.对队列进行出队，并将其左右节点入队
     * 3.重复2
     */
    public List<Integer> levelOrder01(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return list;
    }

    /**
     * ch02找到一棵树最大的宽度
     */
    @Test
    public void test02() {
        Integer[] arr = {1, 3, 2, 5, null, null, 9, 6, 2, null, null, null, null, 7};
        TreeNode node = TreeNode.newLevelTree(arr);
        System.out.println();
        System.out.println("最大宽度为:" + treeWidth01(node));
        System.out.println("最大宽度为:" + treeWidth02(node));
    }

    /**
     * ch02:找到一棵树最大的宽度(去掉空节点)
     * 哈希表思路：在层序遍历时动态将子节点和其对应的层级放入hashMap中
     * 1.准备三个变量分别记录当前层级、当前层宽度与最大宽度
     * 2.预先将头节点入队，并将节点与其层级放入hashMao中
     * 3.对队列进行出队，将其左右节点入队，且将其左右节点放入Queue和hashMap中
     * 4.判断取出的节点层级与当前层级是否相同，如果相同则对当前层宽度++，不同则将当前层级切换到下一层，并将下一层层宽度+1
     * 5.重复4 5直到队列为空
     * 6.由于最后一层没有参与比较，所以在while循环外手动比较
     */
    public int treeWidth01(TreeNode root) {
        int curr = 1, currWidth = 0, maxWidth = -1;
        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        queue.add(root);
        map.put(root, curr);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            Integer level = map.get(node);
            if (curr == level) {
                currWidth++;
            } else {
                maxWidth = Math.max(currWidth, maxWidth);
                curr++;
                currWidth = 1;
            }
            if (node.left != null) {
                queue.add(node.left);
                map.put(node.left, curr + 1);
            }
            if (node.right != null) {
                queue.add(node.right);
                map.put(node.right, curr + 1);
            }
        }
        return Math.max(maxWidth, currWidth);
    }

    /**
     * ch02：滚动边界思路
     * 1.准备两个边界，一个是当前层的边界，一个是下一层的边界；
     * 准备两个变量：一个最宽值max，一个当前宽度width
     * 2.初始化头节点（入队，设置当前层边界）
     * 3.层序遍历二叉树,途中对width进行++,对下一层边界进行更新（下一层边界永远是新入队的（最后入队））
     * 节点碰到当前层边界时表示当前层遍历完成,当前层边界切换到下一层，对max与上一层进行比较，对width进行重置
     */
    public int treeWidth02(TreeNode root) {
        TreeNode currEnd = root, nextEnd = null;
        int max = -1, width = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
                nextEnd = node.left;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextEnd = node.right;
            }
            width++;
            if (node == currEnd) { //抵达当前层终点
                currEnd = nextEnd;
                max = Math.max(max, width);
                width = 0;
            }
        }
        return max;
    }

    /**
     * ch03：二叉树最大宽度包括中间的null节点
     */
    @Test
    public void test03() {
        Integer[] arr = {1, 3, 2, 5, null, null, 9, 6, null, null, null, null, null, 7};
        TreeNode node = TreeNode.newLevelTree(arr);
        System.out.println(widthOfBinaryTree(node));
    }

    /**
     * ch03:二叉树最大宽度包括中间的null节点
     * 思路：
     * 在ch02中我们已经可以求出含有节点的最大宽度
     * 1.我们假设二叉树是一颗完全二叉树，
     * 2.在1的基础上，我们可以计算出当前节点的子节点的索引。我们可以把子节点和其索引放入哈希表中
     * 3.我们先准备一个索引（用于计算每个节点的）和三个边界。
     * 分别表示：一个当前层末尾边界，一个下一层末尾边界，还有一个当前层的起始节点
     * 4.对头节点初始化（入队，设置当前边界，入hashMap）
     * 5.遍历二叉树(途中要从map中获取当前节点的索引)，途中将左右节点（如果有的话）和其索引放入hashMap，
     * 当碰到当前层边界时，从map中取出起始边界的索引和边界的索引，计算出当前层的宽度（末尾索引-起始索引+1）
     * 对max进行比较,更换起始节点（从队列中peek），移到下一层
     */
    public int widthOfBinaryTree(TreeNode root) {
        TreeNode start, currEnd, nextEnd;
        int startIndex = 0, index = 0, max = -1;
        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        queue.add(root);
        map.put(root, index);
        start = root;
        currEnd = root;
        nextEnd = null;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            index = map.get(node);
            if (node.left != null) {
                queue.add(node.left);
                nextEnd = node.left;
                map.put(node.left, index * 2 + 1);
            }
            if (node.right != null) {
                queue.add(node.right);
                nextEnd = node.right;
                map.put(node.right, index * 2 + 2);
            }
            if (node == currEnd) {
                startIndex = map.get(start);
                max = Math.max(max, (index - startIndex + 1));
                start = queue.peek();
                currEnd = nextEnd;
            }
        }
        return max;
    }

    /**
     * ch04:分层层序遍历
     */
    @Test
    public void test04() {
        Integer[] arr = {3, 9, 20, null, null, 15, 7};
        TreeNode node = TreeNode.newLevelTree(arr);
        levelOrder(node).forEach(System.out::print);
    }

    /**
     * ch04:分层层序遍历
     * 队列思路:在ch01的基础上，加上ch02的分层操作
     * 即：用两个边界来判断当前层是否抵达终点，抵达则换层
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode currEnd, nextEnd;
        currEnd = root;
        nextEnd = null;
        //初始化头节点与第一层
        int level = 0;
        lists.add(new ArrayList<>());
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            lists.get(level).add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                nextEnd = node.left;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextEnd = node.right;
            }
            if (currEnd == node) {
                level++;
                lists.add(new ArrayList<>());   //开辟下一层
                currEnd = nextEnd;
            }
        }
        lists.remove(level);    //因为抵达二叉树的终点后依然会开辟下一层，所以要移除掉
        return lists;
    }

    @Test
    public void test05() {
        Integer[] arr = {3, 9, 20, null, null, 15, 7};
        TreeNode node = TreeNode.newLevelTree(arr);
        levelOrder2(node).forEach(System.out::print);
    }


    /**
     * ch05分层层序遍历2
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();    //当前层节点的数量
            List<Integer> level = new ArrayList<>();  //当前层
            for (int i = 0; i < size; i++) {
                TreeNode currNode = queue.poll();
                level.add(currNode.val);
                if (currNode.left != null) {
                    queue.add(currNode.left);
                }
                if (currNode.right != null) {
                    queue.add(currNode.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}
